from operator import mul
from LeetCoder import *


class Solution:

    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True

        p = [i for i in range(100005)]

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def union(x, y):
            px, py = find(x), find(y)
            p[px] = py

        for num in nums:
            if num == 1:
                return False
            k = 2
            tmp = num
            while k <= tmp:
                if tmp % k == 0:
                    union(num, k)
                while tmp % k == 0:
                    tmp //= k
                k += 1

        t = find(nums[0])
        for i in nums:
            if t != find(i):
                return False

        return True


s = Solution()
print(s.canTraverseAllPairs([1, 1]))
# print(s.canTraverseAllPairs([6, 2, 3, 2]))
# print(s.canTraverseAllPairs([2, 3, 6]))
# print(s.canTraverseAllPairs([3, 9, 5]))
# print(s.canTraverseAllPairs([4, 3, 12, 8]))

# num = 24
# k = 2
# tmp = num
# while k <= tmp:
#     if num % k == 0:
#         print(k)
#     while tmp % k == 0:
#         tmp /= k
#     k += 1


class NumberTheoryPrimeFactor:

    def __init__(self, ceil):
        self.ceil = ceil
        self.prime_factor = [[] for _ in range(self.ceil + 1)]
        self.min_prime = [0] * (self.ceil + 1)
        self.get_min_prime_and_prime_factor()
        return

    def get_min_prime_and_prime_factor(self):
        # 模板：计算 1 到 self.ceil 所有数字的最小质数因子
        for i in range(2, self.ceil + 1):
            if not self.min_prime[i]:
                self.min_prime[i] = i
                for j in range(i * i, self.ceil + 1, i):
                    self.min_prime[j] = i

        # 模板：计算 1 到 self.ceil 所有数字的质数分解（可选）
        for num in range(2, self.ceil + 1):
            i = num
            while num > 1:
                p = self.min_prime[num]
                cnt = 0
                while num % p == 0:
                    num //= p
                    cnt += 1
                self.prime_factor[i].append([p, cnt])
        return


nt = NumberTheoryPrimeFactor(10**5 + 1)


class UnionFind:

    def __init__(self, n: int) -> None:
        self.root = [i for i in range(n)]
        self.size = [1] * n
        self.part = n
        return

    def find(self, x):
        lst = []
        while x != self.root[x]:
            lst.append(x)
            # 在查询的时候合并到顺带直接根节点
            x = self.root[x]
        for w in lst:
            self.root[w] = x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] >= self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.root[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        # 将非根节点的秩赋0
        self.size[root_x] = 0
        self.part -= 1
        return True

    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

    def get_root_part(self):
        # 获取每个根节点对应的组
        part = defaultdict(list)
        n = len(self.root)
        for i in range(n):
            part[self.find(i)].append(i)
        return part

    def get_root_size(self):
        # 获取每个根节点对应的组大小
        size = defaultdict(int)
        n = len(self.root)
        for i in range(n):
            size[self.find(i)] = self.size[self.find(i)]
        return size


class Solution:

    def canTraverseAllPairs(self, nums: List[int]) -> bool:
        n = len(nums)
        dct = set(nums)
        ind = defaultdict(list)
        for i in range(n):
            for num, c in nt.prime_factor[nums[i]]:
                ind[num].append(i)
        uf = UnionFind(n)
        for num in ind:
            for i in ind[num]:
                uf.union(ind[num][0], i)
        return uf.part == 1


class Solution:

    def maxStrength(self, nums: List[int]) -> int:
        ans = -inf
        n = len(nums)
        for i in range(1, 1 << n):
            lst = [nums[j] for j in range(n) if i & (1 << j)]
            cur = reduce(mul, lst)
            ans = ans if ans > cur else cur
        return ans